package org.xxl.pathfinder
{
	public class AStar
	{
		private static const COST_STRAIGHT:int = 10;
		
		private static const COST_DIAGONAL:int = 14;
		
		private static const NOTE_ID:int = 0;
		private static const NOTE_OPEN:int = 1;
		private static const NOTE_CLOSED:int = 2;
		
		private var mapTileModel:IMapTileModel;
		private var _maxTry:int;
		
		private var openList:Array;
		private var xList:Array;
		private var yList:Array;
		private var pathScoreList:Array;
		private var movementCostList:Array;
		private var fatherList:Array;
		private var noteMap:Array;
		
		private var openCount:int;
		private var openID:int;
		
		public function AStar(mapTileModel:IMapTileModel, maxTry:int = 500)
		{
			this.mapTileModel = mapTileModel;
			this.maxTry = maxTry;
		}
		
		public function get maxTry():int 
		{
			return _maxTry;
		}
		
		public function set maxTry(value:int):void 
		{
			_maxTry = value;
		}
		
		public function find(startX:int, startY:int, endX:int, endY:int):Array
		{
			initLists();
			
			this.openCount = 0;
			this.openID = -1;
			
			this.openNote(startX, startY, 0, 0, 0);
			
			var currTry:int = 0;
			var currID:int;
			var currNoteX:int;
			var currNoteY:int;
			var aroundNotes:Array;
			
			var checkingID:int;
			
			var cost:int;
			var score:int;
			while (this.openCount > 0)
			{
				if (++currTry > this._maxTry)
				{
					this.destoryLists();
					return null;
				}
				currID = this.openList[0];
				this.closeNote(currID);
				currNoteX = this.xList[currID];
				currNoteY = this.yList[currID];
				
				if (currNoteX == endX && currNoteY == endY)
				{
					return this.getPath(startX, startY, currID);
				}
				aroundNotes = this.getArounds(currNoteX, currNoteY);
				for each(var note:Array in aroundNotes)
				{
					cost = this.movementCostList[currID] + ((note[0] == currNoteX || note[1] == currNoteY)? COST_STRAIGHT:COST_DIAGONAL);
					score = cost + (Math.abs(endX - note[0]) + Math.abs(endY - note[1])) * COST_STRAIGHT;
					if (this.isOpen(note[0], note[1]))
					{
						checkingID = this.noteMap[note[1]][note[0]][NOTE_ID];
						if (cost < this.movementCostList[checkingID])
						{
							this.movementCostList[checkingID] = cost;
							this.pathScoreList[checkingID] = score;
							this.fatherList[checkingID] = currID;
							this.aheadNote(this.getIndex(checkingID));
						}
					}
					else
					{
						this.openNote(note[0], note[1], score, cost, currID);
					}
				}
			}
			this.destoryLists();
			return null;
		}
		
		private function getIndex(id:int):int
		{
			var i:int = 1;
			for each(var i_id:int in this.openList)
			{
				if (i_id == id)
				{
					return i;
				}
				i++;
			}
			return -1;
		}
		
		private function getArounds(x:int, y:int):Array
		{
			var arr:Array = [];
			var checkX:int;
			var checkY:int;
			var canDiagonal:Boolean;
			
			//右
			checkX = x + 1;
			checkY = y;
			var canRight:Boolean = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canRight && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//下
			checkX = x;
			checkY = y + 1;
			var canDown:Boolean = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canDown && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//左
			checkX = x - 1;
			checkY = y;
			var canLeft:Boolean = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canLeft && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//上
			checkX = x;
			checkY = y - 1;
			var canUp : Boolean = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canUp && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//右下
			checkX = x + 1;
			checkY = y + 1;
			canDiagonal = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canDiagonal && canRight && canDown && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//左下
			checkX = x - 1;
			checkY = y + 1;
			canDiagonal = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canDiagonal && canLeft && canDown && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//左上
			checkX = x - 1;
			checkY = y - 1;
			canDiagonal = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canDiagonal && canLeft && canUp && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}
			//右上
			checkX = x + 1;
			checkY = y - 1;
			canDiagonal = this.mapTileModel.isBlock(x, y, checkX, checkY) == 1;
			if (canDiagonal && canRight && canUp && !this.isClosed(checkX, checkY))
			{
				arr.push([checkX, checkY]);
			}

			return arr;
		}
		
		private function isOpen(x:int, y:int):Boolean
		{
			if (noteMap[y] == null)
			{
				return false;
			}
			if (noteMap[y][x] == null)
			{
				return false;
			}
			return this.noteMap[y][x][NOTE_OPEN];
		}
		
		private function isClosed(x:int, y:int):Boolean
		{
			if (this.noteMap[y] == null)
			{
				return false;
			}
			if (noteMap[y][x] == null)
			{
				return false;
			}
			return this.noteMap[y][x][NOTE_CLOSED];
		}
		
		private function getPath(startX:int, startY:int, id:int):Array
		{
			var arr:Array = [];
			var noteX:int = this.xList[id];
			var noteY:int = this.yList[id];
			while (noteX != startX || noteY != startY)
			{
				arr.unshift([noteX, noteY]);
				id = this.fatherList[id];
				noteX = this.xList[id];
				noteY = this.yList[id];
			}
			arr.unshift([startX, startY]);
			this.destoryLists();
			return arr;
		}
		
		/**
		 * 加入开放列表
		 * @param	x
		 * @param	y
		 * @param	score
		 * @param	cost
		 * @param	fatherID
		 */
		private function openNote(x:int, y:int, score:int, cost:int, fatherID:int):void
		{
			this.openCount++;
			this.openID++;
			if (this.noteMap[y] == null)
			{
				this.noteMap[y] = [];
			}
			this.noteMap[y][x] = [];
			this.noteMap[y][x][NOTE_OPEN] = true;
			this.noteMap[y][x][NOTE_ID] = this.openID;
			
			this.xList.push(x);
			this.yList.push(y);
			this.pathScoreList.push(score);
			this.movementCostList.push(cost);
			this.fatherList.push(fatherID);
			
			this.openList.push(openID);
			this.aheadNote(openCount);
		}
		
		private function closeNote(id:int):void
		{
			this.openCount--;
			var noteX:int = this.xList[id];
			var noteY:int = this.yList[id];
			this.noteMap[noteY][noteX][NOTE_OPEN] = false;
			this.noteMap[noteY][noteX][NOTE_CLOSED] = true;
			
			if (this.openCount <= 0)
			{
				this.openCount = 0;
				this.openList = [];
				return;
			}
			this.openList[0] = this.openList.pop();
			this.backNote();
		}
		
		private function backNote():void
		{
			var checkIndex:int = 1;
			var tmp:int;
			var change:int;
			while (true)
			{
				tmp = checkIndex;
				if (2 * tmp <= this.openCount)
				{
					if (this.getScore(checkIndex) > this.getScore(2 * tmp))
					{
						checkIndex = 2 * tmp;
					}
					if (2 * tmp + 1 <= this.openCount)
					{
						if (this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
						{
							checkIndex = 2 * tmp + 1;
						}
					}
				}
				if (tmp == checkIndex)
				{
					break;
				}
				else
				{
					change = this.openList[tmp - 1];
					this.openList[tmp - 1] = this.openList[checkIndex - 1];
					this.openList[checkIndex - 1] = change;
				}
			}
		}
		
		private function aheadNote(index:int):void
		{
			var father:int;
			var change:int;
			while (index > 1)
			{
				father = Math.floor(index * 0.5);
				if (this.getScore(index) < this.getScore(father))
				{
					change = this.openList[index - 1];
					this.openList[index - 1] = this.openList[father - 1];
					this.openList[father - 1] = change;
					index = father;
				}
				else
				{
					break;
				}
			}
		}
		
		private function getScore(index:int):int
		{
			return this.pathScoreList[this.openList[index - 1]];
		}
		
		private function initLists():void
		{
			this.openList = [];
			this.xList = [];
			this.yList = [];
			this.pathScoreList = [];
			this.movementCostList = [];
			this.fatherList = [];
			this.noteMap = [];
		}
		
		private function destoryLists():void
		{
			this.openList = null;
			this.xList = null;
			this.yList = null;
			this.pathScoreList = null;
			this.movementCostList = null;
			this.fatherList = null;
			this.noteMap = null;
		}
	}
}